package Solution.problem074;

/**
 * @program Leetcode
 * @description: 时间0m超过了百分之百，内存42.6超过了百分之5点13，需要优化内存使用
 * @author: lishangsheng
 * @create: 2019/06/11 17:34
 */
public class Solution {
    public static boolean searchMatrix(int[][] matrix, int target) {
        /** 边界判断*/
        int rows = matrix.length;
        if (rows == 0) {
            return false;
        }
        int cols = matrix[0].length;
        if (cols == 0) {
            return false;
        }
        /*二分查找找到对应的行*/
        int rowNUm = getRowNum(matrix, 0, rows - 1, cols, target);
        if (rowNUm == -1) {
            return false;
        }
        /*二分查找在对应行搜索*/
        int[] row = matrix[rowNUm];
        int colNum = getColNum(row, 0, cols - 1, target);
        if (colNum < 0) {
            return false;
        }
        return true;

    }

    private static int getRowNum(int[][] matrix, int startRow, int endRow, int cols, int target) {
        if (startRow > endRow) {
            return -1;
        }
        int mid = (startRow + endRow) / 2;
        int rowStartCol = matrix[mid][0];
        int rowEndCol = matrix[mid][cols - 1];
        if (target < rowStartCol) {
            return getRowNum(matrix, startRow, mid - 1, cols, target);
        } else if (target > rowEndCol) {
            return getRowNum(matrix, mid + 1, endRow, cols, target);
        } else {
            return mid;
        }
    }

    private static int getColNum(int[] row, int startCol, int endCol, int target) {
        if (startCol > endCol) {
            return -1;
        }
        int mid = (startCol + endCol) / 2;

        if (target < row[mid]) {
            return getColNum(row, startCol, mid - 1, target);
        } else if (target > row[mid]) {
            return getColNum(row, mid + 1, endCol, target);
        } else {
            return mid;
        }
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50}};
        System.out.println(searchMatrix(matrix, 11));
        System.out.println(searchMatrix(matrix, 4));
        System.out.println(searchMatrix(matrix, 0));
        System.out.println(searchMatrix(matrix, 51));
        System.out.println(searchMatrix(matrix, 3));
    }
}
